package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	hair := &ListNode{
		Val:  -1000,
		Next: head,
	}
	n1 := hair
	n2 := head.Next
	for n2 != nil {
		for n2 != nil && n2.Val == n1.Next.Val {
			n2 = n2.Next
		}
		// n2 指向第一个不等于 n1.Next 的元素
		if n1.Next.Next == n2 {
			// n1.Next 只出现了一次, 不删除
			n1 = n1.Next
			if n2 != nil {
				n2 = n2.Next
			}
		} else {
			// 删除 n1 与 n2 之间的元素
			n1.Next = n2
		}
	}
	return hair.Next
}

func makeLinked(vals ...int) *ListNode {
	head := &ListNode{Val: vals[0]}
	n := head
	for i, val := range vals {
		if i == 0 {
			continue
		}
		n.Next = &ListNode{
			Val: val,
		}
		n = n.Next
	}
	return head
}

func main() {
	l1 := makeLinked(1, 2, 3, 3, 4, 4, 5)
	ret := deleteDuplicates(l1)
	println(ret)
	l1 = makeLinked(1, 2, 2)
	ret = deleteDuplicates(l1)
	println(ret)
	l1 = makeLinked(1, 2, 2, 3)
	ret = deleteDuplicates(l1)
	println(ret)
	l1 = makeLinked(1, 1)
	ret = deleteDuplicates(l1)
	println(ret)
}
